package com.huangkailong.leetcode;

import java.util.Stack;

/**
 * 给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。<br/>
 * <br/>
 * 进阶：你能尝试使用一趟扫描实现吗？<br/>
 * <br/>
 * <br/>
 * <br/>
 * 示例 1：<br/>
 * <br/>
 * <br/>
 * 输入：head = [1,2,3,4,5], n = 2<br/>
 * 输出：[1,2,3,5]<br/>
 * 示例 2：<br/>
 * <br/>
 * 输入：head = [1], n = 1<br/>
 * 输出：[]<br/>
 * 示例 3：<br/>
 * <br/>
 * 输入：head = [1,2], n = 1<br/>
 * 输出：[1]<br/>
 * <br/>
 * <br/>
 * 提示：<br/>
 * <br/>
 * 链表中结点的数目为 sz<br/>
 * 1 <= sz <= 30<br/>
 * 0 <= Node.val <= 100<br/>
 * 1 <= n <= sz<br/>
 * <br/>
 * @author huangkl
 * @since 1.0.0
 */
public class RemoveNthFromEnd {

    /**
     * 首先计算出链表总长度，然后计算出 n 的位置
     */
    public static ListNode solution1(ListNode head, int n){
        // 计算长度
        int size = 0;
        ListNode p = head;
        while (p != null){
            size++;
            p = p.next;
        }

        // n 是从 1 开始的，而遍历链表也是从 1 开始, i 表示倒数 n+1 的位置
        int i = size-n;
        // p 指向要删除结点的前一个结点
        p = head;
        for (int j = 1; j < i; j++) {
            p = p.next;
        }

        if(i == 0){
            return head.next;
        }

        // 删除结点
        p.next = p.next.next;
        return head;
    }

    /**
     * 先把数据存放到栈中，然后利用栈的特性找到 n+1 的结点
     */
    public static ListNode solution2(ListNode head, int n){
        Stack<ListNode> stack = new Stack<>();
        ListNode p = head;
        while (p != null){
            stack.push(p);
            p = p.next;
        }

        if(stack.isEmpty()){
            return null;
        }

        for (int i = 1; i <= n+1; i++) {
            if(stack.isEmpty()){
                p = null;
                break;
            }
            p = stack.pop();
        }

        if(p != null){
            p.next = p.next.next;
        }

        return p == null ? head.next : head;
    }

    /**
     * 双指针
     */
    public static ListNode solution3(ListNode head, int n){
        if(head == null){
            return null;
        }

        // firstPp 指向 firstP 前一个结点
        ListNode firstPp = null;
        ListNode firstP = head;
        ListNode secondP = head;

        int removeCount = n-1;
        while (secondP.next != null && removeCount > 0){
            secondP = secondP.next;
            removeCount--;
        }

        while (secondP.next != null){
            firstPp = firstP;
            firstP = firstP.next;
            secondP = secondP.next;
        }

        if(firstPp != null){
            firstPp.next = firstPp.next.next;
        }

        return firstPp != null ? head : head.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}


